package org.usmile.algorithms.learn.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * 桶排序
 */
public class BucketSorter {
    public void sort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int max = nums[0];
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }

        int bucketNum = max / 10 + 1;
        List<List<Integer>> buckets = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int num : nums) {
            int bucketIndex = num / 10;
            buckets.get(bucketIndex).add(num);
        }

        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                quickSort(bucket, 0, bucket.size() - 1);
            }
        }
        int i = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                for (int num : bucket) {
                    nums[i++] = num;
                }
            }
        }


    }

    private void quickSort(List<Integer> nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    private int partition(List<Integer> nums, int left, int right) {
        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        int pivot = nums.get(pivotIndex);
        swap(nums, pivotIndex, right);

        int i = left;
        int less = left;
        while (i < right) {
            if (nums.get(i) < pivot) {
                if (i != less) {
                    swap(nums, i, less);
                }
                less++;
            }
            i++;
        }

        swap(nums, less, right);

        return less;
    }

    private void swap(List<Integer> nums, int i, int j) {
        int temp = nums.get(j);
        nums.set(j, nums.get(i));
        nums.set(i, temp);
    }

    public static void main(String[] args) {
        int[] data = new int[]{2, 5, 1, 23, 22, 33, 56, 12, 5, 3, 5, 6, 8, 2, 3, 4};
        new BucketSorter().sort(data);
        System.out.println(Arrays.toString(data));
    }
}
